#include <cctype>
#include <cstdio>
#include <cstring>
#include <queue>

const int N = 100005;
int n, m, c, e_cnt;
int dis[N], heads[N];
bool vis[N];

struct Edge {
  int v, w, nxt;
} e[N << 5];

inline int read() {
  int ch = getchar(), res = 0;
  bool flag = false;
  while (!isdigit(ch)) {
    if (ch == '-') flag = true;
    ch = getchar();
  }
  while (isdigit(ch)) {
    res = (res << 1) + (res << 3) + (ch ^ 48), ch = getchar();
  }
  return flag ? -res : res;
}

std::priority_queue<std::pair<int, int> > pq;

inline void add(int u, int v, int w) {
  e[++e_cnt].v = v, e[e_cnt].w = w, e[e_cnt].nxt = heads[u], heads[u] = e_cnt;
}

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("testdata.in", "r", stdin);
  freopen("testdata.out", "w", stdout);
#endif
#ifndef LOCAL
  freopen("P4366.in", "r", stdin);
  freopen("P4366.out", "w", stdout);
#endif
#endif

  n = read(), m = read(), c = read();
  int u, v, w;
  for (int i = 1; i <= m; ++i) {
    u = read(), v = read(), w = read();
    add(u, v, w);
  }
  for (int i = 0; i <= n; ++i) {
    for (int j = 17; ~j; --j) {
      if ((i ^ (1 << j)) <= n) add(i, i ^ (1 << j), (1 << j) * c);
    }
  }
  int a, b;
  a = read(), b = read();
  memset(dis, 0x3f, sizeof(dis));
  pq.push(std::make_pair(0, a));
  dis[a] = 0;
  while (!pq.empty()) {
    int u = pq.top().second, d = -pq.top().first;
    pq.pop();
    if (u == b) break;
    if (vis[u]) continue;
    vis[u] = true;
    if (d != dis[u]) continue;
    for (int i = heads[u]; i; i = e[i].nxt) {
      int v = e[i].v;
      if (dis[v] > dis[u] + e[i].w) {
        dis[v] = dis[u] + e[i].w;
        pq.push(std::make_pair(-dis[v], v));
      }
    }
  }
  printf("%d", dis[b]);
  return 0;
}
